package leetcode.code0406;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：14 ms, 在所有 Java 提交中击败了21.76%的用户
 *
 * 内存消耗：39.4 MB, 在所有 Java 提交中击败了45.03%的用户
 *
 * 通过测试用例：36 / 36
 */
public class Solution2 implements IDebug {

	public int[][] reconstructQueue(int[][] people) {
		int len = people.length;
		int[][] ans = new int[len][2];
		for (int i = 0; i < len; i++) {
			Arrays.fill(ans[i], -1);
		}
		Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
		int last = people[0][0] - 1;
		int count = 0;
		int p = 0;
		int i = 0;
		while (i < len) {
			if (ans[i][0] != -1) {
				i++;
				continue;
			}
			int[] cur = people[p++];
			if (cur[0] != last) {
				last = cur[0];
				count = 0;
			}
			if (cur[1] - count == 0) {
				ans[i] = cur;
				count++;
				i++;
			} else {
				int tmp = cur[1] - count;
				int to = i;
				while (tmp > 0) {
					if (ans[to][0] == -1) {
						tmp--;
					}
					to++;
				}
				while (to < len && ans[to][0] != -1) {
					to++;
				}
				ans[to] = cur;
				count++;
			}
		}
		return ans;
	}

	@Override
	public void debug1() {
		int[][] e = HelpDebug.str2array1("[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]");
		HelpDebug.compare(e, this.reconstructQueue(HelpDebug.str2array1("[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]")));
	}

	@Override
	public void debug2() {
		int[][] e = HelpDebug.str2array1("[[3,0],[6,0],[7,0],[5,2],[3,4],[5,3],[6,2],[2,7],[9,0],[1,9]]");
		HelpDebug.compare(e,
				this.reconstructQueue(HelpDebug.str2array1("[[9,0],[7,0],[1,9],[3,0],[2,7],[5,3],[6,0],[3,4],[6,2],[5,2]]")));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		int[][] e = HelpDebug.str2array1("[[6,0],[1,1],[8,0],[7,1],[9,0],[2,4],[0,6],[2,5],[3,4],[7,3]]");

		HelpDebug.compare(e,
				this.reconstructQueue(HelpDebug.str2array1("[[2,4],[3,4],[9,0],[0,6],[7,1],[6,0],[7,3],[2,5],[1,1],[8,0]]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug3();
		so.debug2();
		so.debug1();
		so.debug4();

	}

}
